home *** CD-ROM | disk | FTP | other *** search
/ The Atari Compendium / The Atari Compendium (Toad Computers) (1994).iso / files / umich / falcon / programm.ing / nt_dsp1.lzh / NT_DSP1.MSA / FFT / FFTR2B.HLP < prev    next >
Text File  |  1990-01-17  |  4KB  |  66 lines
  1.          Name: FFTR2B.ASM
  2.          Type: Assembler Macro
  3.       Version: 1.1
  4.   Last Change:  2-Oct-86
  5.  
  6.   Description: Radix 2, In-place, Decimation-in-time Complex FFT Macro
  7.  
  8.  This macro performs a complete Fast Fourier Transform (FFT) on complex
  9.  data.  The basic algorithm is the Decimation-in-time (DIT), Radix 2
  10.  FFT algorithm using 24 bit fixed-point arithmetic.  The algorithm uses
  11.  a sine-cosine lookup table for the FFT coefficients (twiddle factors).
  12.  The macro can be called to perform any FFT from 4-32768 points.  Simply
  13.  call it with the arguments of number of FFT points, location of the
  14.  data array and location of the sine-cosine table.  All register
  15.  initialization is performed by this macro.  However, the macro assumes
  16.  that registers which should not be altered by the FFT have already been
  17.  saved by the main program.  This allows the user to fit the FFT macro
  18.  into his application and thus control the context switching overhead.
  19.  No data scaling is performed and no overflow detection is done.
  20.  Modifications to this routine could allow it to be used with the
  21.  scaling modes and thus allow dynamic scaling for each FFT pass.
  22.  
  23.  All data and coefficients are complex, with the real part in X Data
  24.  memory and the imaginary part in Y Data memory.  For an N point FFT,
  25.  the data buffer requires N X Data and N Y Data memory locations.
  26.  The algorithm is performed "in-place", meaning that only one data
  27.  buffer is required for both input and output data.  The input
  28.  data is assumed to be in normal (time-sequential) order and the
  29.  output is in bit-reversed order.  By using the reverse-carry
  30.  address modifier and a separate output data buffer, the output
  31.  data may be easily unscrambled.  Other methods also exist to
  32.  unscramble the output data without a separate output data buffer. 
  33.  The FFTR2B macro uses "twiddle factors" (-cosine and -sine tables)
  34.  stored in data memory.  For maximum speed, the FFT macro performs
  35.  a lookup table operation to get new sine and cosine values for
  36.  each group of butterflies.  A SINCOS macro is available to
  37.  generate these tables.  For an N point FFT, N/2 X Data and N/2
  38.  Y Data locations are required.  Sine and cosine values could be
  39.  calculated in real-time to save data memory at the expense of
  40.  execution time.
  41.  
  42.  The FFTR2B macro is slightly faster than the FFTR2A library macro.
  43.  The speed increase is obtained by splitting the last pass out from
  44.  the triple nested DO loop and giving it a separate DO loop.  The
  45.  reason this is faster is that the FFTR2A inner loop is started
  46.  with a loop count of 1 on the last pass.  Note that the separate last
  47.  pass DO loop uses different addressing modes to increment through the
  48.  butterflies, thus avoiding outer loops.  Additional details are
  49.  included in the source file; however, more algorithm description
  50.  would be required for complete understanding by typical users.  The
  51.  FFTR2B macro can directly replace the FFTR2A macro using the
  52.  calling procedure demonstrated in the FFTR2AT test program.  A
  53.  summary of performance using a 20.5 MHz clock is given below.
  54.  
  55.  Complex
  56.  Points     Int.P,X,Y            Int.P,Ext.X,Y            Ext.P,X,Y
  57.  ------     ---------            -------------            ----------
  58.     16      0.032 msec           0.048 msec               0.072 msec
  59.     64      0.148                0.238                    0.369
  60.    256      0.712                1.175                    1.849
  61.   1024     (3.413)               5.661                    8.958
  62.   4096     (16.01)               26.59                    42.18
  63.  16384     (73.55)               122.3                    194.2
  64.  
  65. where ( ) indicates not possible with internal DSP56000/1 data memory.
  66.